/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-12-12
 * Time:15:15
 */

/**
 * 动态规划:1137. 第 N 个泰波那契数
 * 泰波那契序列 Tn 定义如下：
 * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
 * 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
 * 示例 1：
 * 输入：n = 4
 * 输出：4
 * 解释：
 * T_3 = 0 + 1 + 1 = 2
 * T_4 = 1 + 1 + 2 = 4
 */
public class tribonacci {
    public int tribonacci(int n) {
//        // 处理边界情况
//        if(n == 0){
//            return 0;
//        }
//        if(n == 1 || n == 2){
//            return 1;
//        }
//        //  1.创建 dp 表
//        int[] dp = new int[n + 1];
//        //  2.初始化
//        dp[0] = 0;dp[1] = 1;dp[2] = 1;
//        //  3.填表
//        for(int i = 3;i <= n;i++){
//            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
//        }
//        //  4.返回值
//        return dp[n];

        /**
         * 滚动数组
         */
        if(n == 0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        int a = 0,b = 1,c = 1,s = 1;
        for (int i = 3; i <= n; i++) {
            s = a + b + c;
            a = b;
            b = c;
            c = s;
        }
        return s;
    }
}
